一、DeepWalk [2014]

《DeepWalk: online learning of social representations》

1. network representation 的稀疏性既是优点、也是缺点。稀疏性有助于设计高效的离散算法，但是会使统计学习中的泛化变得更加困难。network 中的机器学习应用（例如 network classification、内容推荐、异常检测、缺失链接预测）必须能够处理这种稀疏性才能生存。

   在论文 《DeepWalk: Online Learning of Social Representations》 中，作者首次将深度学习（无监督特征学习）技术引入到网络分析 （network analysis）中，而深度学习技术已经在自然语言处理中取得了成功。论文开发了一种算法DeepWalk，它通过对 a stream of short random walks 进行建模，从而学习图顶点的社交表示 (social representation) 。

   social representation 是捕获邻域相似性 （neighborhood similarity ）和社区成员关系 （community membership ）的顶点的潜在特征。这些潜在 representation 在低维的、连续的向量空间中对社交关系（social relation ）进行编码。

   DeepWalk 将神经语言模型推广为处理由一组随机生成的游走（walks ）组成的特殊语言。这些神经语言模型已被用于捕获人类语言的语义结构（semantic structure） 和句法结构（syntactic structure ），甚至是逻辑类比（logical analogies） 。DeepWalk 将图作为输入，并生成潜在 representation 作为输出。

   论文的方法应用于经过充分研究的空手道网络（ Karate network ），其结果如下图所示。Karate network 通常以 force-directed 布局呈现，如图 a 所示。图 b 展示了论文方法的输出，其中具有两个潜在维度。除了惊人的相似性之外，我们注意到（图 b）的线性可分部分对应于通过输入图（图 a）中的 modularity maximization 发现的 clusters （以不同顶点颜色表示）。下图中，注意输入图中的社区结构和 embedding 之间的对应关系。顶点颜色表示输入图的 modularity-based clustering 。

   

   为了展示 DeepWalk 在现实世界场景中的潜力，论文评估了它在大型异质图（large heterogeneous graph ）中具有挑战性的 multi-label network classification 问题的性能。在关系分类（ relational classification ）问题中，特征向量之间的链接（ links ）违反了传统的独立同分布的假设。解决这个问题的技术通常使用近似推断技术（approximate inference technique）来利用依赖信息（dependency information ）从而改善分类结果。论文通过学习图的 label-independent representation 来远离这些方法。论文的 representation 质量不受标记顶点选择的影响，因此它们可以在任务之间共享。

   DepWalk 在创建社交维度（ social dimensions ）方面优于其它潜在 representation 方法，尤其是在标记顶点稀疏的情况下。论文的 representation 可以通过非常简单的线性分类器（例如逻辑回归）获得强大的性能。论文的 representation 是通用的，可以与任何分类方法（包括iterative inference method ）结合使用。DeepWalk 实现了所有的这些，同时是一种可简单并行的在线算法。

   论文的贡献如下：

   • 我们引入深度学习作为分析图的工具，从而构建适用于统计建模的鲁棒的 representation 。DeepWalk 学习短的随机游走中存在的结构规律（structural regularity ）。

   • 我们在多个社交网络上广泛评估了我们在多标签分类任务上的表现。在标签稀疏的情况下，我们展示了显著提高的分类性能。在最稀疏的问题上，我们获得了 Micro F1 的 5% - 10% 的提升。在某些情况下，即使训练数据减少 60%，DeepWalk 的 representation 也可以胜过其它竞争对手。

   • 我们通过使用并行实现（ parallel implementation ）来构建 web-scale 图（例如 YouTube） 的 representation ，从而证明了我们算法的可扩展性。此外，我们描述了所需的最小修改从而构建我们方法的 streaming 版本。

2. DeepWalk 是一种学习网络中顶点潜在 representation 的新方法。这些潜在representation 在连续向量空间中编码社交关系，从而很容易被统计模型所利用。DeepWalk 推广了语言模型和无监督特征学习（或深度学习）从单词序列到 graph 的最新进展。

   DeepWalk 使用从截断的随机游走中获得的局部信息，通过将随机游走视为等价的 sentence 来学习潜在 representation 。

   DeepWalk 也是可扩展（scalable ）的。它是一种在线学习算法（online learning algorithm） ，可以构建有用的增量结果，并且可以简单地并行化。这些品质使其适用于广泛的现实世界 application，例如 network classification 和异常检测。

3. DeepWalk 与以前的工作之间的主要区别可以总结如下：

   • DeepWalk 学习潜在的 social representation ，而不是计算 centrality statistics（如 《Leveraging label-independent features for classification in sparsely labeled networks: An empirical study》）、或者 partitioning statistics （如 《Leveraging social media networks for classification》）。

   • DeepWalk 不尝试扩展分类程序本身（通过 collective inference 如《Collective classification in network data》，或者graph kernel如 《Diffuusion kernels on graphs and other discrete input spaces》 ）。

   • DeepWalk 提出了一种仅使用局部信息的、可扩展的、在线方法。大多数方法需要全局信息、并且是离线的。

   • DeepWalk 将无监督representation learning 应用于图。

   接下来，我们讨论 network classification 和无监督 feature　learning 方面的相关工作。

4. 相关工作：

   • Relational Learning：关系分类 relational classification （或者集体分类 collective classification）方法使用数据 item 之间的 links 作为分类过程的一部分。集体分类问题中的精确推断（ exact inference ）是 NP-hard 问题，其解决方案主要集中在近似推断算法。这些近似推断算法可能无法保证收敛。

     与我们的工作最相关的关系分类算法包括：学习clusters（《Leveraging relational autocorrelation with latent group models》）、在附近节点之间添加边（《Using ghost edges for classification in sparsely labeled networks》）、使用 PageRank（《Semi-supervised classification of network data using very few labels》）、通过扩展关系分类来考虑额外的特征(《Multi-label relational neighbor classification using social context features》)，通过这些方法从而合并社区信息（community information） 。

     我们的工作采取了截然不同的方法。我们提出了一种学习网络结构 representation 的程序，而不是新的近似推断算法，然后可以由现有的inference procedure （包括迭代式推断程序）来使用。

     人们还提出了很多从图中生成特征的技术。和这些技术相比，我们将特征创建过程构建为 representation learning 问题。

     人们也提出了 graph kernel （《Graph kernels》） ，从而将关系数据用作分类过程的一部分。但是，除非近似（《Fast random walk graph kernel》），否则它的速度非常慢。我们的方法与 graph kernel 是互补的：我们没有将结构编码为核函数 kernel function 的一部分，而是学习一种 representation，从而允许该 representation 直接用于任何分类方法的特征。

   • 无监督特征学习 Unsupervised Feature Learning：人们已经提出分布式 representation learning 来建模概念之间的结构关系（structural relationship） 。这些 representation 通过反向传播和梯度下降来进行训练。由于计算成本和数值不稳定，这些技术被放弃了十几年。

     最近，分布式计算允许训练更大的模型，并且用于无监督学习的数据出现增长。分布式representation 通常通过神经网络进行训练，这些神经网络在计算机视觉、语音识别、自然语言处理等不同领域取得了进步。

5. DeepWalk 可以挖掘图 $G$$G$ 的局部结构，但是无法挖掘图 $G$$G$ 的整体结构。

1.1 模型

1.1.1 问题定义

1. 考虑社交网络成员的分类问题。正式地，令 $G=(V,E)$$G=(V,E)$ ，其中 $V$$V$ 为图中所有的顶点（也称为网络的成员），$E\subseteq (V\times V)$$E \sube (V\times V)$ 为所有的边。给定一个部分标记的 social network $G_L=(V,E,X,Y)$$G_L = ( V, E, X, Y)$ ，其中：

   • 特征 $X\in {\mathbb{R}}^{|V|\times S}$$X\in \mathbb R^{|V|\times S}$ ，$S$$S$ 为属性空间的维度，$|V|$$|V|$ 为顶点数量。

   • $Y\in {\mathbb{R}}^{|V|\in |\mathcal{Y}|}$$Y\in \mathbb R^{|V|\in |\mathcal Y|}$，$\mathcal{Y}$$\mathcal Y$ 为 label 空间，$|\mathcal{Y}|$$|\mathcal Y |$ 为分类类别数量。

   在传统的机器学习分类 setting 中，我们的目标是学习将 $X$$X$ 的元素映射到标签集合 $Y$$Y$ 的hypothesis $H(\cdot )$$H(\cdot)$ 。在我们的例子中，我们可以利用嵌入在 $G$$G$ 结构中的 example dependence 的重要信息，从而实现卓越的性能。在文献中，这被称作关系分类（relational classification）（或者集体分类）问题。

2. 关系分类的传统方法提出将问题作为无向马尔科夫网络（undirected Markov network ）中的 inference，然后使用迭代式近似推断算法（例如迭代式分类算法 《Iterative classification in relational data》、吉布斯采样《Stochastic relaxation, gibbs distributions, and the bayesian restoration of images》、或者标签松弛算法《On the foundations of relaxation labeling processes》）来计算给定网络结构下标签的的后验分布。

   我们提出了一种不同的方法来捕获网络拓扑信息（network topology information） 。我们没有混合 label 空间从而将其视为特征空间的一部分，而是提出了一种无监督方法，该方法学习了捕获独立于 label 分布的、图结构的特征。

   结构表示（ structural representation ）和标记任务 （labeling task） 的这种分离避免了迭代式方法中可能发生的级联错误（ cascading error ）。此外，相同的 representation 可以用于与该网络有关的多个分类任务（这些分类任务有各自不同的 label）。

   我们的目标是学习 ${\mathbf{X}}_E\in {\mathbb{R}}^{|V|\times d}$$\mathbf X_E\in \mathbb R^{| V|\times d}$ ，其中 $d$$d$ 是一个较低的潜在维度。这些低维 representation 是分布式的，意味着每个社交概念 （ social concept ）都由维度的某个子集来表达，每个维度都有助于低维空间所表达的一组社交概念的集合。

   使用这些结构特征（structural feature） ，我们将扩充属性空间从而帮助分类决策。这些结构特征是通用的，可以与任何分类算法（包括迭代式方法）一起使用。然而，我们相信这些特征的最大效用是：它们很容易与简单的机器学习算法集成。它们在现实世界的网络中可以适当地 scale，正如我们在论文中所展示的。

1.1.2 基础知识

1. 我们寻求具有以下特性的 learning social representation：

   • 适应性（ adaptability）：真实的社交网络在不断演变，新的社交关系不应该要求一遍又一遍地重新训练整个网络。

   • 社区感知（ community aware）：潜在维度之间的距离应该能够代表评估网络成员之间社交相似性（social similarity） 的指标。

   • 低维（low dimensional）：当标记数据稀疏时，低维模型泛化效果更好，并且加快收敛和推断速度。

   • 连续（ continuous）：除了提供社区成员（community membership ）的精细的视图之外，continuous representation 在社区之间具有平滑的决策边界，从而允许更鲁棒的分类。

   我们满足这些要求的方法从短期随机游走的 stream 中学习顶点的 representation，这是最初为语言建模而设计的优化技术。在这里，我们首先回顾随机游走和语言建模（language modeling）的基础知识，并描述了它们的组合如何满足我们的要求。

2. 随机游走（random walk）：我们将以顶点 $v_i$$v_i$ 为 root 的随机游走表示为 ${\mathcal{W}}_{v_i}$$\mathcal W_{v_i}$ 。${\mathcal{W}}_{v_i}$$\mathcal W_{v_i}$ 是一个随机游走过程，其中包含随机变量 $({\mathcal{W}}_{v_i}^1,{\mathcal{W}}_{v_i}^2,\cdots ,{\mathcal{W}}_{v_i}^k)$$\left(\mathcal W_{v_i}^1,\mathcal W_{v_i}^2,\cdots,\mathcal W_{v_i}^k\right)$ 。 ${\mathcal{W}}_{v_i}^k$$\mathcal W_{v_i}^k$ 是一个顶点，它是从顶点 ${\mathcal{W}}_{v_i}^{k-1}$$\mathcal W_{v_i}^{k-1}$ 的邻居中随机选中的。

   随机游走已被用作内容推荐（content recommendation ）和社区检测（community detection） 中各种问题的相似性度量（similarity measure） 。随机游走也是一类输出敏感算法（output sensitive algorithm） 的基础，这类算法使用随机游走来计算局部社区结构信息（local community structure） ，并且计算时间复杂度为 input graph 规模的亚线性（sublinear） 。

   正是这种与局部结构的联系促使我们使用短的随机游走流（stream of short random walks ）作为从网络中提取信息的基本工具。除了捕获社区信息之外，使用随机游走作为我们算法的基础还为我们提供了另外两个理想的特性：

   • 首先，局部探索很容易并行化。多个随机游走器（ random walkers ）（在不同的线程、进程、或者机器中）可以同时探索同一个图的不同部分。

   • 其次，依靠从短的随机游走中获得的信息，可以在不需要全局重新计算的情况下适应图结构的微小变化。我们可以使用新的随机游走，从图变更的区域游走到整个图，从而以亚线性时间复杂度来更新已经训练好的模型。

3. 幂律（power law ）分布：选择在线随机游走作为捕获图结构的原语 （primitive） 之后，我们现在需要一种合适的方法来捕获这些图结构信息。

   如果连通图的 degree 分布遵循幂律分布 （power law）（也叫作 Zipf 定律），那么我们观察到顶点出现在短随机游走中的频率也遵循幂律分布。自然语言中的单词遵循类似的分布，语言模型（language modeling ）技术解释了这种分布行为。为了强调这种相似性，我们在下图中展示了两个不同的幂律分布：第一个来自一个图上的一系列短随机游走，第二个来自于英文维基百科的 100,000 篇文章的文本。图 a 给出了short random walk 中，顶点出现频次的分布。图 b 给出了英文维基百科的 10 万篇文章中，单词的频次分布。

   

   我们工作的一个核心贡献是这样的一种思想：用于建模自然语言（其中单词频率遵循幂律分布）的技术也可以复用于建模网络中的社区结构。

   接下来我们将回顾语言建模中不断发展的工作，并将其转换为学习满足我们标准的顶点 representation 。

1.1.3 语言模型

1. 语言模型的目标是估计特定单词序列在语料库 corpus 中出现的可能性。正式地，给定一个单词序列 $\mathcal{S}=(w_0,w_1,\cdots ,w_n)$$\mathcal S=(w_0,w_1,\cdots,w_n)$，其中 $w_i\in \mathbb{V}$$w_i\in \mathbb V$（$\mathbb{V}$$\mathbb V$ 为词典 vocabulary），我们希望在整个训练语料库上最大化 $\text{Pr}(w_n\mid w_0,w_1,\cdots ,w_{n-1})$$\text{Pr}(w_n\mid w_0,w_1,\cdots,w_{n-1})$ 。

   最近在 representation learning 方面的工作聚焦于使用概率神经网络（probabilistic neural network ）来构建单词的 general representation，从而将语言建模的范围扩展到其原始目的之外。

2. 在这项工作中，我们提出了语言建模的泛化，以通过短随机游走流来探索图。这些随机游走可以被认为是一种特殊语言的短句（ short sentence ）和短语 （short phrase）。我们进行直接的类比，从而在随机游走中，给定到目前为止访问的所有顶点序列来估计观察到顶点 $v_i$$v_i$ 的可能性，即 $\text{Pr}(v_i\mid (v_1,v_2,\cdots ,v_{i-1}))$$\text{Pr}(v_i\mid (v_1,v_2,\cdots,v_{i-1}))$ 。

   我们的目标是学习潜在 representation，而不仅仅是节点共现（node co-occurrence ）的概率分布，因此我们引入一个映射函数 $\mathrm{\Phi }:V\to {\mathbb{R}}^{|V|\times d}$$\Phi: V \rightarrow \mathbb R^{| V|\times d}$ 。该映射函数 $\mathrm{\Phi }(\cdot )$$\Phi(\cdot)$ 将图中每个顶点 $v$$v$ 映射到一个潜在的 social representation 。

   即：我们想要的是顶点 representation，而不是预估这个随机游走序列出现的概率。

   实际上，我们使用 free parameters 的矩阵 $\mathbf{\Phi }\in {\mathbb{R}}^{|V|\times d}$$\mathbf\Phi\in \mathbb R^{|V|\times d}$ 来表达 $\mathrm{\Phi }(\cdot )$$\Phi(\cdot)$，这在稍后将被用作我们的 ${\mathbf{X}}_E$$\mathbf X_E$ 。然后，问题变成了似然估计：

   $$\text{Pr}(v_i\mid (\mathrm{\Phi }(v_1),\mathrm{\Phi }(v_2),\cdots ,\mathrm{\Phi }(v_{i-1})))$$

   然而，随着游走序列长度的增加，计算这个目标函数变得不可行。

   因为 sentence 越长，它出现的频次越低，样本过于稀疏。

3. 最近，在语言模型中的放松条件使得这个预测问题得到了解决。

   • 首先，我们不是使用上下文来预测缺失单词（ missing word），而是使用一个单词来预测上下文。

   • 其次，上下文由出现在给定单词左侧和右侧的单词组成。

   • 最后，我们消除了对问题的顺序约束（ ordering constraint ）。即，模型需要最大化任何单词出现在上下文中的概率，而无需知道上下文与目标单词的偏移量。

   应用到顶点建模中，这得到了优化问题：

   $$\underset{\mathbf{\Phi }}{min}-\log \text{Pr}(\{v_{i-w},\cdots ,v_{i-1},v_{i+1},\cdots ,v_{i+w}\}\mid \mathrm{\Phi }(v_i))$$

   其中 $w$$w$ 为上下文窗口尺寸。

   我们发现这些放松条件对于 social representation learning 是特别理想的。

   • 首先，顺序独立性假设（ order independence assumption ）更好地捕获了随机游走的 nearness 的 sense。

   • 其次，这种松弛条件对于通过构建一大批小模型来加速训练非常有用，因此一次给定一个顶点。

   解决上式中的优化问题将得顶点representation，这些 representation 捕获了顶点之间在局部图结构（local graph structure ）中的相似性。具有相似邻域的顶点将获得相似的 representation（编码了 co-citation 相似性），并允许对机器学习任务进行泛化。

4. 通过结合截断的随机游走和神经语言模型，我们制定了一种满足我们所有期望特性的方法。

   • 该方法生成低维的社交网络 representation，并存在于连续向量空间中。

   • 该方法生成的 representation 对社区成员的潜在形式 latent form 进行编码。

   • 并且，由于该方法输出有用的 intermediate representation ，因此它可以适应不断变化的网络拓扑结构。

1.1.4 DeepWalk

1. 与任何语言建模算法一样，DeepWalk 唯一需要的输入是语料库和词表 $\mathbb{V}$$\mathbb V$ 。DeepWalk 将一组截断的短随机游走视为语料库，将图的顶点视为词表（$\mathbb{V}=V$$\mathbb V = V$） 。虽然在训练之前知道随机游走中顶点集合 $V$$V$ 和顶点的频率分布是有益的，但是DeepWalk 在不知道顶点集合的情况下也可以工作。

2. DeepWalk 算法主要由两部分组成：随机游走生产器、更新过程。

   • 随机游走生成器random walk generator ：以图 $G$$G$ 作为输入并均匀随机采样一个顶点 $v_i$$v_i$ 作为随机游走 ${\mathcal{W}}_{v_i}$$\mathcal W_{v_i}$ 的 root 。随机游走从最近访问的顶点的邻域中均匀采样，直到游走序列长度达到最大长度 $t$$t$ 。

     虽然在我们的实验中，随机游走序列的长度设置为固定的（固定为 $t$$t$ ），但是理论上没有限制它们都是相同的长度。这些随机游走可能会重启，即返回 root 的传送概率 （teleport probability），但是我们的初步结果并为表明使用重启能带来任何优势。

   • 更新过程：基于 SkipGram 语言模型来更新参数 $\mathbf{\Phi }$$\mathbf\Phi$ 。SkipGram 是一种语言模型，可最大化在一个句子中出现在窗口 $w$$w$ 内的单词之间的共现概率。

     在随机游走中，对于出现在窗口 $w$$w$ 中的所有上下文，我们最大化给定当前顶点 $v_j$$v_j$ 的 representation 的条件下，上下文顶点 $u_k$$u_k$ 出现的概率。

3. DeepWalk 算法：

   • 输入：

     • 图 $G(V,E)$$G( V, E)$

     • 上下文窗口尺寸 $w$$w$

     • embedding size $d$$d$

     • 每个节点开始的随机游走序列数量 $\gamma$$\gamma$

     • 每条随机游走序列长度 $t$$t$

   • 输出：顶点 representation 矩阵 $\mathbf{\Phi }\in {\mathbb{R}}^{|V|\times d}$$\mathbf \Phi\in \mathbb R^{| V|\times d}$

   • 算法步骤：

     • representation 初始化：从均匀分布中采样，得到初始的 $\mathbf{\Phi }$$\mathbf\Phi$ 。

     • 从 $V$$V$ 构建一颗二叉树 binary tree $T$$T$

       建立二叉树是为了后续 SkipGram 算法采用 Hierarchical Softmax

     • 遍历，$i=0,\cdots ,\gamma$$i=0,\cdots,\gamma$，遍历过程：

       • 随机混洗顶点：$\mathcal{O}=\text{Shuffle}(V)$$\mathcal O = \text{Shuffle}( V)$

         每次遍历的开始，随机混洗顶点。但是这一步并不是严格要求的，但是它可以加快随机梯度下降的收敛速度。

       • 对每个顶点 $v_i\in \mathcal{O}$$v_i\in \mathcal O$：

         • 利用随机游走生成器生成随机游走序列：${\mathcal{W}}_{v_i}=\text{RandomWalk}(G,v_i,t)$$\mathcal W_{v_i} = \text{RandomWalk}( G,v_i,t)$

         • 采用 SkipGram 算法来更新顶点的representation：$\text{SkipGram}(\mathbf{\Phi },{\mathcal{W}}_{v_i},w)$$\text{SkipGram}(\mathbf\Phi,\mathcal W_{v_i},w)$

4. SkipGram 算法：

   • 输入：

     • 当前的顶点 representation矩阵 $\mathbf{\Phi }\in {\mathbb{R}}^{|V|\times d}$$\mathbf \Phi\in \mathbb R^{| V|\times d}$

     • 单条随机游走序列 ${\mathcal{W}}_{v_i}$$\mathcal W_{v_i}$

     • 上下文窗口尺寸 $w$$w$

     • 学习率 $\alpha$$\alpha$

   • 输出：更新后的顶点 representation矩阵 $\mathbf{\Phi }\in {\mathbb{R}}^{|V|\times d}$$\mathbf \Phi\in \mathbb R^{| V|\times d}$

   • 算法步骤：

     • 对每个顶点 $v_j\in {\mathcal{W}}_{v_i}$$v_j\in \mathcal W_{v_i}$：

       • 对窗口内每个顶点 $u_k\in {\mathcal{W}}_{v_i}[j-w:j+w]$$u_k\in \mathcal W_{v_i}[j-w:j+w]$：

         $$\begin{array}{c}J(\mathbf{\Phi })=-\log \text{Pr}(u_k\mid \mathrm{\Phi }(v_j))\\ \mathbf{\Phi }=\mathbf{\Phi }-\alpha \times {\mathrm{\nabla }}_{\mathbf{\Phi }}J\end{array}$$

5. Hierarchical Softmax： 计算 $\text{Pr}(u_k\mid \mathrm{\Phi }(v_j))$$\text{Pr}(u_k\mid \Phi(v_j))$ 是不容易的，因为这个概率的分母（归一化因子）计算代价太高（计算复杂度为 $O(|V|)$$O(|V|)$）。如果我们将顶点分配给二叉树的叶节点，那么预测问题就变为最大化树中特定路径的概率。如果到顶点 $u_k$$u_k$ 的路径由一系列树节点 $(b_0,b_1,\cdots ,b_{\lceil \log |V|\rceil })$$(b_0,b_1,\cdots,b_{\lceil \log | V|\rceil})$ （$b_0$$b_0$ 为 root，$b_{\lceil \log |V|\rceil }=u_k$$b_{\lceil \log | V|\rceil}=u_k$）标识，则有：

   $$\text{Pr}(u_k\mid \mathrm{\Phi }(v_j))=\prod _{l=1}^{\lceil \log |V|\rceil }\text{Pr}(b_l\mid \mathrm{\Phi }(v_j))$$

   现在 $\text{Pr}(b_l\mid \mathrm{\Phi }(v_j))$$\text{Pr}(b_l\mid \Phi(v_j))$ 可以通过分配给节点 $b_l$$b_l$ 的父节点的二分类器来建模。这降低了计算 $\text{Pr}(u_k\mid \mathrm{\Phi }(v_j))$$\text{Pr}(u_k\mid \Phi(v_j))$ 的复杂度，计算复杂度从 $O(|V|)$$O(| V|)$ 降低到 $O(\log |V|)$$O(\log | V|)$ 。

   我们可以通过为随机游走中的高频顶点分配树中更短的路径来进一步加快训练过程。霍夫曼编码用于减少树中高频元素的访问次数。

6. DeepWalk 模型参数规模为 $O(d|V|)$$O(d|V|)$，并且使用随机梯度下降来优化这些参数。导数是通过反向传播算法来估计的。SGD 的学习率在最初时设置为 0.025，然后随着目前为止看到的顶点数量呈线性下降。

7. DeepWalk 算法整体如下图所示。

   • 图 a：短随机游走序列的生成过程。

   • 图 b：在随机游走 ${\mathcal{W}}_{v_4}$$\mathcal W_{v_4}$ 上滑动一个长度为 $2w+1$$2w+1$ 的窗口，将中心顶点 $v_1$$v_1$ 映射到它的 representation $\mathrm{\Phi }(v_1)$$\Phi(v_1)$ 。

   • 图 c：Hierarchical Softmax 在对应于从 root 到 $v_3$$v_3$ 的路径上的概率序列来分解 $\text{Pr}(v_3\mid \mathrm{\Phi }(v_1))$$\text{Pr}(v_3\mid \Phi(v_1))$ 。$\text{Pr}(v_5\mid \mathrm{\Phi }(v_1))$$\text{Pr}(v_5\mid \Phi(v_1))$ 也是类似的。

     representation $\mathbf{\Phi }$$\mathbf\Phi$ 被更新从而最大化中心顶点 $v_1$$v_1$ 与它的上下文 $\{v_3,v_5\}$$\{v_3,v_5\}$ 共现的概率。

   

1.1.5 并行化

1. 社交网络随机游走中的顶点频率分布和语言中的单词分布都遵循幂律分布。这会导致低频顶点的长尾效应，因此，对 $\mathbf{\Phi }$$\mathbf\Phi$ 的更新本质上将是稀疏的（即，同时对同一个顶点进行更新的概率很低）。 这将允许我们在多个 worker 的情况下使用随机梯度下降的异步版本 ASGD。

   鉴于我们的更新是稀疏的，并且我们没有利用锁来访问模型共享参数，ASGD 将实现最佳收敛速度。虽然我们在单台机器上使用多线程进行实验，但是已经证明了 ASGD 具有高度可扩展性，可用于非常大规模的机器学习。

   下图展示了并行化 DeepWalk 的效果。结果表明：随着我们将 worker 数量增加到 8，处理 BlogCatalog 和 Flickr 网络的加速是一致的。结果还表明，与串行执行 DeepWalk 相比，并行化 DeepWalk 的预测性能没有损失。

   

1.1.6 变体

1. 这里我们讨论我们方法的一些变体，我们认为这些变体可能会引起人们的兴趣。

2. 流式（ streaming）：我们方法的一个有趣变体是流式方法，它可以在不了解整个图的情况下实现。在这个变体中，来自图中的短随机游走直接传递给 representation learning 代码，并直接更新模型。

   这里需要对学习过程进行一些修改：

   • 首先，不再使用衰减的学习率。相反，我们可以将学习率 $\alpha$$\alpha$ 初始化为一个小的常量。这需要更长的时间来学习，但是在某些 application 中可能是值得的。

   • 其次，我们不能再构建参数树 tree of parameters。如果 $V$$V$ 的基数 cardinality 是已知的（或者有界），我们可以为这个最大值构建 Hierarchical Softmax tree。当首次看到顶点时，可以将它分配给剩余的叶节点之一。如果我们有能力估计顶点分布的先验，我们仍然可以使用霍夫曼编码来减少高频元素的访问次数。

3. 非随机的游走：有些图是用户与一系列元素（如网站上页面的导航）交互的副产品而创建的。当通过这种非随机游走的 stream 来创建图时，我们可以使用这个过程直接为建模阶段提供游走数据。以这种方式采样的图不仅会捕获与网络结构相关的信息，还会捕获与路径遍历频率相关的信息。

   以我们的观点来看，这个变体还包括语言建模。sentence 可以被视为经过适当设计的语言网络的、有目的的游走，而像 SkipGram 这样的语言模型旨在捕获这种行为。

   这种方法可以与流式变体结合使用，从而在不断演化的网络上训练特征，而无需显式地构建整个图。使用这种技术维护的 representation 可以实现 web-scale 的分类，而无需处理 web-scale 图的麻烦。

1.2 实验

1. 数据集：

   • BlogCatalog 数据集：由博客作者提供的社交关系网络。标签代表作者提供的主题类别。

   • Flickr 数据集：Flickr网站用户之间的关系网络。标签代表用户的兴趣组，如“黑白照片”。

   • YouTube 数据集：YouTube 网站用户之间的社交网络。标签代表用户的视频兴趣组，如“动漫、摔跤”。

   

2. baseline 方法：为了验证我们方法的效果，我们和一些 baseline 方法进行比较。

   • 谱聚类（ SpectralClustering）：从图 $G$$G$ 的 normalized graph Laplacian 矩阵 $\tilde{\mathbf{L}}$$\tilde{\mathbf L}$ 中计算到的 $d$$d$ 个最小的特征向量，构成图的representation。使用 $\tilde{\mathbf{L}}$$\tilde{\mathbf L}$ 的特征向量隐含地建设图割（graph cuts ）对分类有用。

   • Modularity：从图 $G$$G$ 的 Modularity $\mathbf{B}$$\mathbf B$ 计算得到 top-d 个特征向量，构成了图的representation。$\mathbf{B}$$\mathbf B$ 的特征向量编码了关于 $G$$G$ 的modular graph partition 信息。使用它们作为特征假设 modular graph partition 对于分类有用。

   • EdgeCluster：基于 k-means 聚类算法对图 $G$$G$ 的邻接矩阵进行聚类。事实证明它的性能可以和 Modularity 相比，并且可以扩展到那些超大规模的图，这些图太大而难以执行谱分解（spectral decomposition） 。

   • wvRN： weighted-vote Relational Neighbor 是一个关系分类器 （relational classier ）。给定顶点 $v_i$$v_i$ 的邻居 ${\mathcal{N}}_i$$\mathcal N_i$，wvRN 通过邻居结点的加权平均来预估 $P(y_i\mid {\mathcal{N}}_i)$$P(y_i\mid \mathcal N_i)$：

     $$P(y_i\mid {\mathcal{N}}_i)=\frac{1}{Z}\sum _{v_j\in {\mathcal{N}}_i}{w}_{i,j}P(y_j\mid {\mathcal{N}}_j)$$

     其中 $Z$$Z$ 为归一化系数。

     该方法在实际网络中表现出惊人的良好性能，并被推荐为优秀的关系分类（relational classification ）的 baseline。

   • Majority：选择训练集中出现次数最多的标签作为预测结果（所有样本都预测成一个值）。

3. 评估指标：对于多标签分类问题，我们采用 Macro-F1 和 Micro-F1 作为评估指标。

   • Macro-F1 ：根据整体的混淆矩阵计算得到的 $F_1$$F_1$ 值。

   • micro-F1：先根据每个类别的混淆矩阵计算得到各自的 $F_1$$F_1$ 值，然后对所有 $F_1$$F_1$ 值取平均。

   另外我们采用模型提取的特征训练 one-vs-rest 逻辑回归分类器，根据该分类器来评估结果。

   我们随机采样一个比例为 $T_R$$T_R$ 的带标签顶点作为训练集，剩余标记节点作为测试集。我们重复该过程 10 次，并报告 Macro-F1 的平均性能和 Micro-F1 的平均性能。

   注意，DeepWalk 是无监督的 representation learning 方法，因此训练过程是无需 label 数据的。这里的标记数据是在无监督学习之后，利用学到的顶点 representation 进行有监督分类，分类算法为逻辑回归，从而评估顶点 representation 的效果。

4. 实验配置：

   • 对所有模型，我们使用由 LibLinear 实现的 one-vs-rest 逻辑回归进行分类。

   • DeepWalk的超参数为 $\gamma =80,w=10,d=128$$\gamma = 80, w=10, d=128$ 。

   • 对于 SpectralClustering, Modularity, EdgeCluster 等方法，我们选择 $d=500$$d=500$ 。

1.2.1 实验结果

2. BlogCatalog数据集：我们评估 $T_R=10\mathrm{\%}\sim 90\mathrm{\%}$$T_R= 10\% \sim 90\%$ 的结果。结果如下表，粗体表示每一列最佳结果。

   结论：

   • DeepWalk 性能始终优于 EdgeCluster,Modularity,wvRN 。

     事实上当 DeepWalk 仅仅给出 20% 标记样本来训练的情况下，模型效果优于其它模型 90% 的标记样本作为训练集。

   • 虽然 SpectralClustering 方法更具有竞争力，但是当数据稀疏时 DeepWalk 效果最好：对于 Macro-F1 指标，$T_R\le 20\mathrm{\%}$$T_R \le 20\%$ 时 DeepWalk 效果更好；对于Micro-F1 指标，$T_R\le 60\mathrm{\%}$$T_R\le 60\%$ 时 DeepWalk 效果更好。

   • 当仅标记图中的一小部分时，DeepWalk 效果最好。因此后面实验我们更关注稀疏标记图sparsely labeled graph 。

3. Flickr 数据集：我们评估 $T_R=1\mathrm{\%}\sim 10\mathrm{\%}$$T_R= 1 \% \sim 10\%$ 的结果。结果如下表，粗体表示每一列最佳结果。结论与前面的实验一致。

   • 在 Micro-F1 指标上，DeepWalk 比其它基准至少有 3% 的绝对提升。

   • 在 Micro-F1 指标上，DeepWalk 只需要 3% 的标记数据就可以打败其它方法 10% 的标记数据，因此 DeepWalk 的标记样本需求量比基准方法少 60% 。

   • 在 Macro-F1 指标上，DeepWalk 性能接近 SpectralClustring，击败了所有其它方法。

   

4. YouTube 数据集：我们评估 $T_R=1\mathrm{\%}\sim 10\mathrm{\%}$$T_R= 1 \% \sim 10\%$ 的结果。结果如下表，粗体表示每一列最佳结果。

   由于 YouTube 规模比前面两个数据集大得多，因此我们无法运行两种基准方法 SpecutralClustering, Modularity 。

   • DeepWalk 性能远超 EdgeCluster 基准方法：

     • 当标记数据只有 1% 时，DeepWalk 在 Micro-F1 指标上相对 EdgeCluster 有 14% 的绝对提升，在 Macro-F1 指标上相对 EdgeCluster 有 10% 的绝对提升。

     • 当标记数据增长到 10% 时，DeepWalk 提升幅度有所下降。DeepWalk 在 Micro-F1 指标上相对 EdgeCluster 有 3% 的绝对提升，在 Macro-F1 指标上相对 EdgeCluster 有 4% 的绝对提升。

   • DeepWalk 能扩展到大规模网络，并且在稀疏标记环境中表现出色。

   

1.2.2 参数敏感性

1. 为评估超参数的影响，我们在 Flickr 和 BlogCatalog 数据集上进行实验。我们固定窗口大小 $w=10$$w=10$ 和游走长度 $t=40$$t=40$ 。然后我们改变潜在维度 $d$$d$ 、每个顶点开始的随机游走数量 $\gamma$$\gamma$、可用的训练数据量 $T_R$$T_R$ ，从而确定它们对于网络分类性能的影响。

2. 考察不同 $d$$d$ 的效果：

   • 图 a1 和 图 a3 考察不同 $d$$d$ 和不同 $T_R$$T_R$ 的效果。Flickr 和 BlogCatalog 数据集上模型的表现一致：模型最佳尺寸 $d$$d$ 取决于训练样本的数量。

     注意：Flickr 的 1% 训练样本和 BlogCatalog 的 10% 训练样本，模型的表现差不多。

   • 图 a2 和图 a4 考察不同 $d$$d$ 和不同 $\gamma$$\gamma$ 的效果。在不同 $\gamma$$\gamma$ 取值上，模型性能对于不同 $d$$d$ 的变化比较稳定。

     • 从 $\gamma =30$$\gamma = 30$ 开始继续提高 $\gamma$$\gamma$ 时模型的效果提升不大，因此 $\gamma =30$$\gamma = 30$ 几乎取得最好效果。继续提升效果，计算代价上升而收益不明显。

     • 不同的数据集中，不同 $\gamma$$\gamma$ 值的性能差异非常一致，尽管 FLICKR 包含边的数量比 BLOGCATALOG 多一个数量级。

   这些结论表明：我们的方法可以得到各种size 的有用模型。另外，模型性能取决于模型看到的随机游走数量，模型的最佳维度取决于可用的训练样本量。

   

3. 考察不同 $\gamma$$\gamma$ 的影响。图 b1 和 b3 考察不同 $d$$d$ 的效果，图 b2 和 b4 考察了不同 $T_R$$T_R$ 的效果。

   实验结果表明，它们的表现比较一致：增加 $\gamma$$\gamma$ 时开始可能有巨大提升，但是当 $\gamma >10$$\gamma \gt 10$ 时提升效果显著下降。

   这些结果表明：仅需要少量的随机游走，我们就可以学习有意义的顶点潜在表示。